package a00_LeetCode.TopK;
import java.util.*;

/**
 * @Author quan
 * @Description 前K个高频单词
 * 出现频率最高的K个单词，若频率相同，则按字典序；输出结果按照频率由高到低排序
 * @Date 2023/4/3 18:51
 */


public class Num692_topKFrequent {
    /**
     * 难点1：从高到低排序：链表的头插： 降序
     * 难点2：按字典序排序，升序
     * 难点3：2与1之间的矛盾性：因为i字典序<love字典序，但是之前保存元素使用的是头插，这样会造成love在i之前。
     * 所以在这里我们需要让JDK误认为love在i之前，所以让s2.compareTo(s1)
     */
    public List<String> topKFrequent(String[] words, int k) {
        //1、用Map保存每个单词以及出现的频次
        Map<String,Integer> map = new HashMap<>();
        //for循环后，每个map中保存了每个单词以及出现的频次
        for (String str: words) {
            if(map.containsKey(str)){
                int value = map.get(str);
                map.put(str, value+1);
            }else{
                map.put(str,1);
            }
        }
        //2、定义优先级队列和判定规则：小堆定义，new接口，定义比较方式：频次和字典序
        Queue<String> queue = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                int times1 = map.get(o1);
                int times2 = map.get(o2);
                return times1==times2 ? o2.compareTo(o1) : times1-times2;
            }
        });
        //3、扫描map保存出现频率最高的K个单词
        for (Map.Entry<String,Integer> entry: map.entrySet()){
            queue.offer(entry.getKey());
            if(queue.size()>k){
                queue.poll();
            }
        }
        //最后queue保存的就是前K个出现频次最高的单词
        LinkedList<String> result = new LinkedList<>();
        while (!queue.isEmpty()){
            result.addFirst(queue.poll());
        }
        return result;
    }
}

